package com.topcoder.srm510;

public class TheLuckyBasesDivTwo {
	public long find(long n) {
		if (n==4 || n==7) return -1;
		if (n < 7) return 0;
		
		long count = 0;
		for (long b=5; b*b <= n; b++) {
			long t = n;
			while (t > 0) {
				long r = t % b;
				if (r != 4 && r != 7) break;
				t /= b;
			}
			if (t == 0) count++;
		}
		
		if (n%4 == 0 && n >= 4*5 + 4) count++;
		if (n%4 == 3 && n >= 4*8 + 7) count++;
		if (n%7 == 4 && n >= 7*8 + 4) count++;
		if (n%7 == 0 && n >= 7*8 + 7) count++;
		
		return count;
	}
}
